#include<bits/stdc++.h>
using namespace std;

bool check(string &source, string &target){
    int i = 0, j = 0;
    while(i < source.length() && j < target.length()){
        if(source[i] == target[j]){
            j++;
        }
        i++;
    }
    return j == target.length();
}

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(), dictionary.end(), [&](string &a, string &b) -> bool{
            if(a.length() != b.length())return a.length() > b.length();
            return a.compare(b) < 0;
        });

        for(int i = 0; i < dictionary.size(); i++){
            if(dictionary[i].length() > s.length())continue;
            if(!check(s, dictionary[i]))continue;
            return dictionary[i];
        }
        return "";
    }
};

/**
 * 2021.9.14
 * 自定义排序 + 子序列匹配
 * 子序列匹配部分可以用 dp 进一步压缩时间...
 * .....................................
 */